#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Queue:
    def __init__(self):
        self.queue = []

    def push(self, value):
        self.queue.append(value)

    def pop(self):
        return self.queue.pop(0)

    def top(self):
        return self.queue[0]

    def __bool__(self):
        return bool(self.queue)

class Solution:
    """
    @param root: A Tree
    @return: Level order a list of lists of integer
    """
    def levelOrder(self, root):
        # DFS
        self.ret = []
        self.rec_dfs_level_order(root, 1)

        return self.ret

    def rec_dfs_level_order(self, node, depth):
        if node is None:
            return

        if len(self.ret) < depth:
            assert len(self.ret) == depth-1
            self.ret.append([])

        self.ret[depth-1].append(node.val)
        self.rec_dfs_level_order(node.left, depth+1)
        self.rec_dfs_level_order(node.right, depth+1)

    def _levelOrder(self, root):
        # write your code here
        self.ret = []
        self.queue = Queue()

        self.queue.push(root)
        self.queue.push('end')
        self.ret.append([])

        while self.queue:
            is_end = False

            node = self.queue.pop()

            print('Node [%s]' % getattr(node, 'val', 'None'))
            node_next = self.queue.top()
            if node_next == 'end':
                is_end = True
                self.queue.pop()
                # print('match end')

            if node is not None:
                self.ret[-1].append(node.val)
                print('push left [%s]' % getattr(node.left, 'val', 'None'))
                print('push right[%s]' % getattr(node.right, 'val', 'None'))
                self.queue.push(node.left)
                self.queue.push(node.right)

            if is_end and self.queue:
                print('push end')
                self.queue.push('end')
                self.ret.append([])

            print()

        self.ret.pop()
        return self.ret


# class Solution:
#     """
#     @param root: A Tree
#     @return: postorder in ArrayList which contains node values.
#     """

#     def postorderTraversal(self, root):
#         self.ret = []

#         self.rec_postorder(root)
#         # self.non_rec_postorder(root)

#         return self.ret

#     def non_rec_postorder(self, root):
#         self.stack = []
#         self.stack.append( [root, 0] )         # 相当于递归首先从root开始遍历
#         # self.stack.append(root)         # 相当于递归首先从root开始遍历

#         while self.stack:
#             node_state = self.stack[-1]
#             node, state = node_state
#             if not node:
#                 self.stack.pop()
#                 continue

#             # print(node.val)
#             # 判断left, right
#             if state == 0:
#                 self.stack.append([node.left, 0])
#                 node_state[1] = 1
#             elif state == 1:
#                 self.stack.append([node.right, 0])
#                 node_state[1] = 2
#             else:
#                 assert state == 2
#                 self.ret.append(node.val)
#                 self.stack.pop()

#     def rec_postorder(self, node):
#         # print('rec')
#         if not node:
#             return

#         # print(node.val)
#         # print(self.ret)
#         # print(id(self.ret))
#         self.rec_postorder(node.left)
#         self.rec_postorder(node.right)
#         self.ret.append(node.val)


def main():
    print("start main")
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    root = TreeNode(0)
    # root.left = None
    root.right = n1
    n1.left = n2

    s = Solution()
    ret = s.levelOrder(root)
    print(ret)

if __name__ == "__main__":
    main()
